package date_202403

import (
	"strconv"
	"strings"
)

//306. 累加数
//
//累加数 是一个字符串，组成它的数字可以形成累加序列。
//
//一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。
//
//给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。
//
//说明：累加序列里的数，除数字 0 之外，不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
//
//
//
//示例 1：
//
//输入："112358"
//输出：true
//解释：累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
//示例 2：
//
//输入："199100199"
//输出：true
//解释：累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
//
//
//提示：
//
//1 <= num.length <= 35
//num 仅由数字（0 - 9）组成
//
//
//进阶：你计划如何处理由过大的整数输入导致的溢出?

func isAdditiveNumber(num string) bool {
	if len(num) < 3 {
		return false
	}

	for i := 1; i <= len(num)/2; i++ {
		for j := 1; j <= len(num)/2; j++ {
			if isAdditiveNumberWithIdx(num, i, j) {
				return true
			}
		}
	}
	return false
}

func isAdditiveNumberWithIdx(num string, firstLen int, secondLen int) bool {
	firstNumStr := num[0:firstLen]
	secondNumStr := num[firstLen : firstLen+secondLen]

	for nextBeginIdx := firstLen + secondLen; nextBeginIdx < len(num); {
		if (len(firstNumStr) > 1 && strings.HasPrefix(firstNumStr, "0")) ||
			(len(secondNumStr) > 1 && strings.HasPrefix(secondNumStr, "0")) {
			return false
		}
		firstNum, _ := strconv.Atoi(firstNumStr)
		secondNum, _ := strconv.Atoi(secondNumStr)
		expectThirdNum := strconv.Itoa(firstNum + secondNum)
		if nextBeginIdx+len(expectThirdNum) > len(num) {
			return false
		}
		thirdStr := num[nextBeginIdx : nextBeginIdx+len(expectThirdNum)]
		if len(thirdStr) > 1 && strings.HasPrefix(thirdStr, "0") {
			return false
		}
		if thirdStr != expectThirdNum {
			return false
		}
		if nextBeginIdx+len(expectThirdNum) == len(num) {
			return true
		}
		firstNumStr = secondNumStr
		secondNumStr = thirdStr
		nextBeginIdx = nextBeginIdx + len(expectThirdNum)
	}
	return false
}
